{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "840825d1",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'\\nstack优点：\\n1.提供后进先出的存取方式；\\nstack缺点：\\n1.存取其他项很慢\\n\\n'"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\"\"\"\n",
    "stack优点：\n",
    "0.有序结构的优点\n",
    "1.数据存取方式——后进先出 \n",
    "2.数据修改方式——栈顶去除，栈顶增加\n",
    "\n",
    "3.栈顶发生——读，增，删\n",
    "4.栈底不发生——任何操作\n",
    "\n",
    "【不会出现在队中修改数据的情况】 \n",
    "【尾部=栈顶，头部=栈底】\n",
    "\n",
    "stack缺点：\n",
    "1.存取其他项很慢\n",
    "\n",
    "stack意义：\n",
    "1.能用入栈时间为t的数据去检验，时间为t+1的数据 【进行左右括号匹配】\n",
    "2.能够优先读取最新入栈的数据                   【读取辗转相除法的正确顺序】\n",
    "3.递归算法\n",
    "4.撤销与重做操作的实现\n",
    "\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "46e63d44",
   "metadata": {},
   "outputs": [],
   "source": [
    "# 实现stack\n",
    "class Stack:\n",
    "    def __init__(self):\n",
    "        self.items = []   # 初始化栈，以list为基础\n",
    "    \n",
    "    def isEmpty(self):           # 判断stack是否为空\n",
    "    \n",
    "        return self.items == []  # 判断栈的items属性是否为空列表；并给出判断结果 (True or False)\n",
    "    \n",
    "    def push(self,item):         #  接受一个元素，并把元素放入栈中\n",
    "    \n",
    "        self.items.append(item)   \n",
    "    \n",
    "    def pop(self):               #  把stack的末尾元素删除后  \n",
    "        return self.items.pop()\n",
    "    \n",
    "    def peek(self):              #  把stack的最后一位元素返回出来    \n",
    "        return self.items[len(self.items)-1]  \n",
    "    \n",
    "    def size(self):              # 返回stack的元素个数\n",
    "        return len(self.items)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "id": "e9ad5f5b",
   "metadata": {},
   "outputs": [
    {
     "ename": "IndexError",
     "evalue": "list index out of range",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mIndexError\u001b[0m                                Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-44-e669dc85e85d>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[1;32m      1\u001b[0m \u001b[0ms\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mStack\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 2\u001b[0;31m \u001b[0ms\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mpeek\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;32m<ipython-input-9-4379522000dd>\u001b[0m in \u001b[0;36mpeek\u001b[0;34m(self)\u001b[0m\n\u001b[1;32m     10\u001b[0m         \u001b[0;32mreturn\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mitems\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mpop\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     11\u001b[0m     \u001b[0;32mdef\u001b[0m \u001b[0mpeek\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 12\u001b[0;31m         \u001b[0;32mreturn\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mitems\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mlen\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mitems\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m-\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     13\u001b[0m     \u001b[0;32mdef\u001b[0m \u001b[0msize\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     14\u001b[0m         \u001b[0;32mreturn\u001b[0m \u001b[0mlen\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mitems\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mIndexError\u001b[0m: list index out of range"
     ]
    }
   ],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "id": "77f2ddd7",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "正确\n",
      "[]\n"
     ]
    }
   ],
   "source": [
    "# 检查语句的括号匹配是否规范【左右括号是否匹配】\n",
    "'''\n",
    "1.语句读到的第一个括号一定是左括号；最后一个括号一定是右括号【但不要钱最左/右端一定是括号】\n",
    "2.左右括号数目必须一一对应\n",
    "3.括号里面的表达式需要先计算【多层括号，先计算最里面的】\n",
    "4.计算优先级  () > */ > + - \n",
    "'''\n",
    "([)]\n",
    "\n",
    "z = Stack()\n",
    "s = \"2+(2+(3+4))*3+()\"\n",
    "zz = True\n",
    "for i in s:\n",
    "    i = str(i)\n",
    "    if i in [\"(\",\")\",\"[\",\"]\",\"{\",\"}\"]:\n",
    "         if z.isEmpty():\n",
    "             if   (i == \"(\" or i == \"{\" or i == \"[\"):\n",
    "                 z.push(i)\n",
    "             elif (i == \")\" or i == \"}\" or i == \"]\"):\n",
    "                 print('语法错误')\n",
    "                 zz = False\n",
    "                 break\n",
    "         else:\n",
    "            if z.peek()==\"(\" and i==\")\":\n",
    "                z.pop()\n",
    "            elif z.peek()==\"{\" and i==\"}\":\n",
    "                z.pop()\n",
    "            elif z.peek()==\"[\" and i==\"]\":\n",
    "                z.pop()\n",
    "            else:\n",
    "                 print('语法错误')\n",
    "                 zz = False\n",
    "                 break\n",
    "\n",
    "        \n",
    "if z.isEmpty() and zz:\n",
    "    print('正确')\n",
    "    print(z.items)\n",
    "else:\n",
    "    print('语法错误')\n",
    "    print(z.items)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "id": "792fa2ef",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['F']"
      ]
     },
     "execution_count": 59,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#2.辗转相除法\n",
    "num = 15\n",
    "jinzhi = 16\n",
    "basestr = '0123456789ABCDEFGHLJKLMN'\n",
    "s = Stack()\n",
    "\n",
    "while num>=jinzhi:\n",
    "  \n",
    "    i = basestr[num%jinzhi]\n",
    "    s.push(i)\n",
    "    num = num//jinzhi\n",
    "\n",
    "s.push(basestr[num%jinzhi])\n",
    "\n",
    "s.items"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "id": "a0b10de8",
   "metadata": {},
   "outputs": [
    {
     "ename": "IndexError",
     "evalue": "list index out of range",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mIndexError\u001b[0m                                Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-84-90a28de95f26>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[1;32m     35\u001b[0m                 \u001b[0mz\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mpop\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     36\u001b[0m             \u001b[0;32mif\u001b[0m \u001b[0mdj\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mi\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m<=\u001b[0m \u001b[0mdj\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mz\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mpeek\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 37\u001b[0;31m                 \u001b[0;32mwhile\u001b[0m \u001b[0mdj\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mi\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m<=\u001b[0m \u001b[0mdj\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mz\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mpeek\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     38\u001b[0m                     \u001b[0ml\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mappend\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mz\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mpeek\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     39\u001b[0m                     \u001b[0mz\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mpop\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-9-4379522000dd>\u001b[0m in \u001b[0;36mpeek\u001b[0;34m(self)\u001b[0m\n\u001b[1;32m     10\u001b[0m         \u001b[0;32mreturn\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mitems\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mpop\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     11\u001b[0m     \u001b[0;32mdef\u001b[0m \u001b[0mpeek\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 12\u001b[0;31m         \u001b[0;32mreturn\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mitems\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mlen\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mitems\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m-\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     13\u001b[0m     \u001b[0;32mdef\u001b[0m \u001b[0msize\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     14\u001b[0m         \u001b[0;32mreturn\u001b[0m \u001b[0mlen\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mitems\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mIndexError\u001b[0m: list index out of range"
     ]
    }
   ],
   "source": [
    "#3.后序表达式\n",
    "\n",
    "z = Stack()\n",
    "s = \"2+(2+(3+4))*3\"  # 2234++3*+\n",
    "\n",
    "# 1. +  - () tongji\n",
    "# 2. + * 时不要压\n",
    "# 3. * + 时 把*压出去\n",
    "# 4. + + 时 把+压出去   i<= peek  \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "# 1+2*3+4\n",
    "\n",
    "\n",
    "\n",
    "dj = {\"+\":1,\"-\":1,\"*\":2,\"/\":2,\"(\":0}\n",
    "\n",
    "l = []\n",
    "for i in s:\n",
    "    if not i in [\"+\",\"-\",\"*\",\"/\",\"(\",\")\"]:\n",
    "        l.append(i)\n",
    "    elif i == \"(\":\n",
    "        z.push(i)\n",
    "    elif i ==\")\" and not z.isEmpty():\n",
    "        z.pop()\n",
    "        while z.peek()!=\"(\":\n",
    "            l.append(z.peek())\n",
    "            z.pop()\n",
    "    else:\n",
    "        while (not z.isEmpty()) and (dj[z.peek()]>=dj[i]):\n",
    "            l.append(z.peek())\n",
    "            z.pop()\n",
    "        z.push(i)\n",
    "    \n",
    "        \n",
    "        \n",
    "while not z.isEmpty():\n",
    "    l.append(z.peek())\n",
    "    z.pop()               \n",
    "            \n",
    "if z.isEmpty() and zz:\n",
    "    print(l)\n",
    "else:\n",
    "    print('语法有误')\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "id": "f4bd0d7e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 81,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "z.isEmpty()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ed079530",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a847f1e7",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.8"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
